package cg.studio.algorithm.permutation;

import java.util.ArrayList;
import java.util.List;

/**
 * the algorithm is not complete. take "abcd" for example. think it over
 * 
 * Generate Permutation by shift the chars in a String
 * 
 * from left to right:
 * ab  --a--> ba
 *     --b--> ab
 * 
 * abc --a--> bac --a--> bca
 *     --b--> cba --b--> cab
 *     --c--> acb --c--> abc
 * 
 * @author Bright Chen
 *
 */
public class ShiftPermutator implements Permutator
{
  /**
   * return all possible permutation of String <str>
   * @param str
   * @return
   */
  public List< char[] > permutate( String str )
  {
    char[] chars = str.toCharArray();
    
    // a list of char[], each char[] is a permutation
    List< char[] > results = new ArrayList< char[] >();
    
    // i represents which position of char in the array we are going to shifting. we should shift leng-1 times
    for( int shiftingCharIndex=0; shiftingCharIndex<chars.length; ++shiftingCharIndex )
    {
      char shiftingChar = chars[ shiftingCharIndex ];
      int shiftTimes = 0;
//      for( int shiftToPosition=increaseIndex( shiftingCharIndex, chars.length ); 
//           shiftTimes < chars.length-1; 
//          shiftToPosition = increaseIndex( shiftToPosition, chars.length ), ++shiftTimes )
      for( int shiftToPosition=1; 
          shiftTimes < chars.length-1; 
         ++shiftToPosition, ++shiftTimes )
      { 
        char[] copiedChars = copyChars( chars.length, chars, increaseIndex( shiftingCharIndex, chars.length ), shiftToPosition );
        copiedChars[shiftToPosition] = shiftingChar;
        results.add( copiedChars );
      }
    }
    return results;
  }
  
  // 
  protected int increaseIndex( int index, int size )
  {
    return ( index == size-1 ) ? 0 : index+1;
  }
  
  /**
   * create an array of char, which capacity is <capacity>,
   * and copy data from <original>[ 1, <firstPartSize> ), 
   * and leave the value of index <firstPartSize> to empty, and copy the value after that;
   * for example copyChars( 4, "abcd", 1, 1 ) returns "b cd"
   * 
   * @param capacity the capacity of the array which will be created
   * @param source the original char array
   * @param startIndex the index of the original char array, the method will copy chars start from this index
   * @param emptyIndex the index of the created array which will be leave as empty
   * 
   * @return the created char array
   */
  protected char[] copyChars( int capacity, char[] source, int startIndex, int emptyIndex )
  {
    char[] chars = new char[ capacity ];
    
    int sourceIndex = startIndex;
    int destIndex = 0;
    for( ; destIndex < emptyIndex; sourceIndex=increaseIndex( sourceIndex, capacity ), ++destIndex )
    {
      chars[ destIndex ] = source[ sourceIndex ];
    }
    ++destIndex;
    for( ; destIndex < capacity; sourceIndex=increaseIndex( sourceIndex, capacity ), ++destIndex )
    {
      chars[ destIndex ] = source[ sourceIndex ];
    }
    return chars;
  }
}
